#include <bits/stdc++.h>

using namespace std;

// 无序数组中第K大的元素
// 测试链接 : https://leetcode.cn/problems/kth-largest-element-in-an-array/

class Solution 
{
    int first = 0, last = 0;

    void partition(vector<int>& nums, int l, int r, int x)
    {
        first = l, last = r;
        int i = l;
        while(i <= last)
        {
            if(nums[i] == x) ++i;
            else if(nums[i] < x) swap(nums[first++], nums[i++]);
            else swap(nums[last--], nums[i]);
        }
    }

    // 如果arr排序的话，在i位置的数字是什么
    int randomizedSelect(vector<int>& nums, int i)
    {
        int ans = 0;
        for(int l = 0, r = nums.size() - 1; l <= r;)
        {
            // 随机这一下，常数时间比较大
			// 但只有这一下随机，才能在概率上把时间复杂度收敛到O(n)
            partition(nums, l, r, nums[rand() % (r - l + 1) + l]);
            // 因为左右两侧只需要走一侧
			// 所以不需要临时变量记录全局的first、last
			// 直接用即可
            if(i < first)
                r = first - 1;
            else if(i > last)
                l = last + 1;
            else
            {
                ans = nums[i];
                break;
            }
        }
        return ans;
    }

public:
    // 随机选择算法，时间复杂度O(n)
    int findKthLargest(vector<int>& nums, int k) 
    {
        srand(time(nullptr));
        return randomizedSelect(nums, nums.size() - k);    
    }
};


class Solution 
{
    int getRandom(vector<int>& nums, int left, int right)
    {
        int r = rand();
        return nums[r % (right - left + 1) + left];
    }

    int qsort(vector<int>& nums, int left, int right, int k)
    {
        if(left == right) return nums[left];

        int key = getRandom(nums, left, right);
        int l = left - 1, r = right + 1, i = left;
        while(i < r)
        {
            if(nums[i] < key) swap(nums[++l], nums[i++]);
            else if(nums[i] == key) ++i;
            else swap(nums[--r], nums[i]);
        }

        int c = right - r + 1, b = r - l - 1;
        if(c >= k) return qsort(nums, r, right, k);
        else if(b + c >= k) return key;
        else return qsort(nums, left, l, k - b - c);
    }

public:
    int findKthLargest(vector<int>& nums, int k) 
    {
        srand(time(nullptr));
        return qsort(nums, 0, nums.size() - 1, k);    
    }
};